//
//  CCRecusion.h
//  leetcode
//
//  Created by hellobike07499 on 2019/9/25.
//  Copyright © 2019 hellobike07499. All rights reserved.
//

#ifndef CCRecusion_h
#define CCRecusion_h
#include <vector>
#include <map>
#include <istream>
#include <sstream>
#include "CCLink.h"

class CCRecusion{
public:
    void test(){
        test5();
    }
    
    void test1(){
        vector<char> ss = {'a', 'b', 'c'};
        reverseString(ss);
        
    }
    
    void test2(){
        vector<int> a = getRow(3);
    }
    void test3(){
        cout << fib(10) << endl;
    }
    
    void test4(){
//        cout << "-1 , 0 ::" << myPow(-1, 0) << endl;
//        cout << "2, -1 ::" << myPow(2, -1) << endl;
//        cout << "2, 5 ::" << myPow(2, 5) << endl;
        
        cout << "2, -2147483648 ::" << myPow(2, -2147483648) << endl;
    }
    
    void test5(){
        cout << "1, 1, " << kthGrammar(1, 1) << endl;
        
        cout << "2, 1, " << kthGrammar(2, 1) << endl;
        cout << "4, 5, " << kthGrammar(4, 5) << endl;
    }
private:
    void reverseString(vector<char>& s) {
        if(s.size() <= 1){
            return;
        }
        char f = s[0];
        s.erase(s.begin());
        reverseString(s);
        
        s.insert(s.begin() + s.size(), f);
    }
    
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next){
            return head;
        }
        
        ListNode *tmp = head->next;
        head->next = swapPairs(tmp->next);
        tmp->next = head;
        
        return tmp;
    }
    //给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
    vector<int> getRow(int rowIndex) {
        if(rowIndex <= 0){
            return vector<int>(1, 1);
        }
        vector<int> value = getRow(rowIndex - 1);
        
        vector<int> current(rowIndex + 1, 1);
        for (int i = 0; i < (rowIndex + 1); i++) {
            if(i == 0 || i == rowIndex){
                current[i] = 1;
                continue;
            }
            current[i] = value[i - 1] + value[i];
        }
        return current;
    }
    
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        
        ListNode *tmp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        
        return tmp;
    }
    
    map<int, int> cache;
    int fib(int N) {
        if(N < 2) return N;
        
        map<int, int>::iterator item = cache.find(N);
        if(item != cache.end()) {
            return item->second;
        }
        
        int v = fib(N - 1) + fib(N - 2);
        cache[N] = v;
        return v;
    }
    
    //求x的n次幂
    double myPow(double x, int n) {
        double tmpX = x;
        long tmpN = n;
        if(n < 0){
            tmpX = 1/tmpX;
            tmpN = tmpN * -1;
        }
        if(n == 0 || x == 1.0f){
            return 1;
        }
        
        if(tmpN == 1){
            return tmpX;
        }
        
        double result = 1;
        if(tmpN % 2 != 0){
            result = tmpX;
            tmpN = tmpN - 1;
        }
        
        double half = myPow(tmpX, (unsigned int)tmpN/2);
        return half * half * result;
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    
    string getNGrammar(int N){
        if(N == 1) return "0";
        string last = getNGrammar(N - 1);
        
        stringbuf str;
        ostream buffer(&str);
        
        for (int i = 0; i < last.length(); i++) {
            if(last.c_str()[i] == '0'){
                buffer << "01";
            }else{
                buffer << "10";
            }
        }
        return str.str();
    }
    int kthGrammar(int N, int K) {
        string getG = getNGrammar(N);
        if(K > getG.length() || K < 0){
            return 0;
        }
        
        return (getG.c_str()[K-1] == '0' ? 0 : 1);
    }
};

#endif /* CCRecusion_h */
